package KMP_conpleteness;

import java.util.Arrays;

public class KMP {
    //创建next数组
    private static int[] Next(String s) {
        int[] next = new int[s.length() + 1];
        int count = 0;
        int index = 1;
        next[index] = count;
        for (int i = 1; i < s.length(); i++) {
            count = 0;
            int slow = 0;//从头开始
            int faster = i / 2;//从中间开始
            for (int j = faster; j < i; j++) {
                if (s.charAt(slow) == s.charAt(faster) && slow != faster) {
                    slow++;
                    count++;
                } else if (s.charAt(slow) != s.charAt(faster) ) {
                    slow = 0;
                    count = slow;
                    if(s.charAt(slow) == s.charAt(faster)) {
                        faster--;//退回slow 并就在这个faster在比较}
                        j--;//在这个点在找一次
                    }
                }
                faster++;
            }
            next[index++] = count + 1;
        }
        return next;

    }

    public static int Find(String texts, String target) {
        //造next数组
        int[] next = Next(target);

        //将目标字符串转换为数组方便操作
        char[] chars = target.toCharArray();
        chars = Arrays.copyOf(chars, chars.length + 1);
        for (int i = chars.length - 1; i > 0; i--) {
            chars[i] = chars[i - 1];
        }
        chars[0] = '0';

        //find
        int index_n = 1;
        int flag = 0;
        int i = 0;
        for (i = 0; i < texts.length(); i++) {
            if (texts.charAt(i) != chars[index_n]) {
                i += next[index_n];
                i--;//从跟新的这个点开始找
                index_n = 1;
            } else {
                index_n++;
            }
            if (index_n == chars.length) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            return -1;
        }
        return i - chars.length + 2;
    }
}
